{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e92d3e03-964a-4dd0-b608-db32a3b1ed96",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/word-search-ii"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60be26e2-802c-49c0-a429-f87a4eba35a2",
   "metadata": {},
   "source": [
    "# 2023/01/13\n",
    "\n",
    "\n",
    "Timeout\n",
    "\n",
    "\n",
    "```python\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        #2023/01/13 08:21\n",
    "\n",
    "        def is_location_valid(location):\n",
    "            y,x = location\n",
    "            #print(y,x)\n",
    "            if y < 0 or y > len(board)-1:\n",
    "                return False\n",
    "            if len(board) > 0:\n",
    "                if x < 0 or x > len(board[0])-1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def trace_a_word(current_location, word, location_path_list):\n",
    "            #print(current_location, word, location_path_list)\n",
    "            if len(word) == 0:\n",
    "                # that word exists in the board\n",
    "                return True\n",
    "            if current_location in location_path_list:\n",
    "                return False\n",
    "            if not is_location_valid(current_location):\n",
    "                return False\n",
    "            #print(current_location)\n",
    "            y,x = current_location\n",
    "            current_char = board[y][x]\n",
    "            if current_char == word[0]:\n",
    "                result = []\n",
    "                # top\n",
    "                new_location = (y-1, x)\n",
    "                result.append(trace_a_word(new_location, word[1:], (location_path_list + [current_location]).copy()))\n",
    "                # right\n",
    "                new_location = (y, x+1)\n",
    "                result.append(trace_a_word(new_location, word[1:], (location_path_list + [current_location]).copy()))\n",
    "                # bottom\n",
    "                new_location = (y+1, x)\n",
    "                result.append(trace_a_word(new_location, word[1:], (location_path_list + [current_location]).copy()))\n",
    "                # left\n",
    "                new_location = (y, x-1)\n",
    "                result.append(trace_a_word(new_location, word[1:], (location_path_list + [current_location]).copy()))\n",
    "                return any(result)\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def find_a_word_in_board(word):\n",
    "            ok = False\n",
    "            for y, row in enumerate(board):\n",
    "                if ok:\n",
    "                    break\n",
    "                for x, value in enumerate(row):\n",
    "                    ok = trace_a_word((y,x), word, [])\n",
    "                    # print(ok)\n",
    "                    # ok = True\n",
    "                    if ok:\n",
    "                        break\n",
    "            return ok\n",
    "        \n",
    "        result_list = []\n",
    "        for word in words:\n",
    "            result = find_a_word_in_board(word)\n",
    "            if result == True:\n",
    "                result_list.append(word)\n",
    "        return result_list\n",
    "\n",
    "        #2023/01/13 09:02\n",
    "        #debug until 09:10\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ee6b5b5b-b7e6-4e29-a681-e7f90bf02aa9",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}